打起精神來，今天有比昨天更好一點！

這題，我對他的解釋是，現在有未知的圖，我有些node跟node之間的線索，用線索去把這個圖的全貌拼湊出來(講得好像在解謎一樣XD)。

簡單講就是現在這張圖，只有它送過來指定的node配對中，兩點的公因數有大於threshold，兩點之間就有連線。
　
　
　

思路

感覺這題是在圖的基礎上，問你怎麼找兩數的公因數。
　
　
　

看題目時，眼睛要在睜大一點

因為題目問的是：請問我指定的配對有沒有path可以連通，所以兩點之間即使沒有直達的edge，也可能有path存在，所以不能單單只是找最大公因數。

所以思路會改為，先判斷公因數，更新圖，如果沒有符合條件的公因數，再用traversal找一遍。
　

程式題

class Solution {
public:
    vector<int> parent ;
    
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        vector<bool> answer(queries.size());
   
        if (!threshold) {
            fill(answer.begin(), answer.end(), true);
            return answer;
        }
        
        parent = vector<int>(n+1) ;
        for (int i = 0; i < parent.size(); i++) parent[i] = i;
        
        for (int z = threshold + 1; 2*z <= n; z++)
            for (int x = 2; x*z <= n; x++) 
                unionfunc(z, x*z);
        
        for (int i = 0; i < queries.size(); i++)
            answer[i] = find(queries[i][0]) == find(queries[i][1]);
        
        return answer;
    }
private:
    int find(int u) {
        if (parent[u] != u)
            return find(parent[u]);
        return u;
    }
    
    void unionfunc(int u, int v) {
        parent[find(v)] = parent[find(u)];
    }
};

補充

這題跟第一天Graph-Tree: uva 615 Is It A Tree?一樣使用並查集，也體會到我還沒有很熟這種資料結構，至少我沒辦法像adj list那樣熟練。

並查集是了解了沒錯，但是參不透中間那兩個for是幹啥用的！

C++ 筆記

Line 30: Char 10: error: declaration of anonymous union must be a definition
void union(vector& parent, int u, int v) {

union是保留字

　
　
參考：
https://leetcode.com/problems/graph-connectivity-with-threshold/discuss/899462/Extremely-useful-Union-Find-class-Feel-Free-to-Reuse
https://www.youtube.com/watch?v=ayW5B2W9hfo